Schur Numbers

Introduction

Step 1

Step 2

Step 3

Step 4

Step 5

Schur numbers for other numbers of colors

Number of colors $n$Schur number $S(n)$
11
24
313
444
5160
6$\geq 536$
7$\geq 1680$

Definition and Formal Statement

The Schur number $S(n)$ is defined as the largest integer $N$ such that the set: $$\{1, 2, 3, \dots, N\}$$ can be colored with $n$ colors in such a way that no monochromatic solution exists to the equation: $$x + y = z$$ where $x, y, z \in \{1, 2, \dots, N\}$.

Formal Statement

Example

Historical Background

Key Milestones

Context

Connection to Ramsey Theory

Schur numbers are deeply connected to Ramsey theory, which studies unavoidable patterns in large, structured systems.

Schur Numbers as a Ramsey-Type Problem

Relationship to Van der Waerden Numbers

Key Insight

Exercises

  1. Verify that $S(1) = 1$ by explaining why $\{1,2\}$ cannot be 1-colored without producing $1+1=2$.

    Answer to Exercise 1

    Verify that $S(1) = 1$ by explaining why $\{1,2\}$ cannot be 1-colored without producing $1+1=2$.

    To verify that $S(1) = 1$, we need to show two things:

    1. The set $\{1\}$ can be 1-colored without a monochromatic solution to $x+y=z$.
      • If we 1-color the set $\{1\}$, the number $1$ is assigned the single available color (let's say, blue). The only possible values for $x, y, z$ in the equation $x+y=z$ within the set $\{1\}$ would be $x=1, y=1, z=1$. However, $1+1=2$, and $2$ is not in the set $\{1\}$. Therefore, no solution to $x+y=z$ exists within $\{1\}$, and vacuously, there are no monochromatic solutions.
    2. The set $\{1,2\}$ cannot be 1-colored without producing a monochromatic solution to $x+y=z$.
      • If we attempt to 1-color the set $\{1,2\}$, both $1$ and $2$ must be assigned the same single color (e.g., blue).
      • Consider the equation $x+y=z$. We can find a solution within $\{1,2\}$: $$1 + 1 = 2$$
      • In this case, $x=1$, $y=1$, and $z=2$. Since all numbers are assigned the same color (blue), $x$, $y$, and $z$ are all blue. This constitutes a monochromatic solution.

    Since $\{1\}$ can be 1-colored without a monochromatic solution, but $\{1,2\}$ cannot, the largest integer $N$ for which the set $\{1, \dots, N\}$ can be 1-colored without a monochromatic solution is $N=1$. Therefore, $S(1)=1$.

  2. Provide an explicit 3-coloring of $\{1,2,\dots,13\}$ that avoids monochromatic solutions to $x+y=z$.
  3. Compare Schur numbers $S(n)$ with Van der Waerden numbers $W(r,k)$ for small values. For example, compute $W(2,3)$ and discuss how it differs conceptually from $S(2)$.

    Answer to Exercise 3

    Compare Schur numbers $S(n)$ with Van der Waerden numbers $W(r,k)$ for small values. For example, compute $W(2,3)$ and discuss how it differs conceptually from $S(2)$.

    Understanding Van der Waerden Numbers

    The Van der Waerden number $W(r,k)$ is defined as the smallest integer $N$ such that if the integers $\{1, 2, \dots, N\}$ are colored with $r$ different colors, there must exist a monochromatic arithmetic progression of length $k$. An arithmetic progression of length $k$ is a sequence of numbers $a, a+d, a+2d, \dots, a+(k-1)d$ for some integers $a$ and $d > 0$.

    Computing $W(2,3)$

    We want to find $W(2,3)$, which is the smallest $N$ such that any 2-coloring of $\{1, 2, \dots, N\}$ contains a monochromatic arithmetic progression of length 3. Let's try to construct 2-colorings that avoid such a progression for increasing $N$.

    Let the two colors be Red (R) and Blue (B).

    • $N=1$: R (No AP of length 3)
    • $N=2$: RR (No AP of length 3)
    • $N=3$: RRB (No AP of length 3), RBR (No AP of length 3), RBB (No AP of length 3). If all are R: RRR (AP: 1,2,3). So $N=3$ can be colored without AP3. e.g., RRB.
    • $N=4$: RRBB (No AP of length 3).
    • $N=5$: RRBBR (No AP of length 3). Try to construct an AP3: $1,2,3$ (R,R,B - no), $1,3,5$ (R,B,R - no), $2,3,4$ (R,B,B - no), etc.
    • $N=6$: RRBBRR (No AP of length 3)
    • $N=7$: RRBBRRB (No AP of length 3)
    • $N=8$: RRBBRRBB (No AP of length 3)

    It has been proven that for $N=8$, it is possible to construct a 2-coloring without a monochromatic AP of length 3 (e.g., RRBBRRBB or BBRRBB RR). However, for $N=9$, any 2-coloring must contain a monochromatic arithmetic progression of length 3.

    Therefore, $W(2,3) = 9$.

    Conceptual Differences from $S(2)$

    As established in the notebook and Exercise 1, the Schur number $S(2) = 4$. This means that the set $\{1, 2, 3, 4\}$ can be 2-colored without a monochromatic solution to $x+y=z$, but $\{1, 2, 3, 4, 5\}$ cannot.

    Let's compare $S(2)$ and $W(2,3)$:

    FeatureSchur Number $S(n)$Van der Waerden Number $W(r,k)$
    DefinitionLargest $N$ such that $\{1,\dots,N\}$ can be $n$-colored without monochromatic $x+y=z$.Smallest $N$ such that any $r$-coloring of $\{1,\dots,N\}$ has a monochromatic AP of length $k$.
    Problem TypeAdditive combinatorics (sums)Arithmetic progressions
    Values$S(2) = 4$$W(2,3) = 9$
    Example Case$S(2)$ implies $\{1,2,3,4\}$ can be 2-colored (e.g., $\textcolor{red}1 \textcolor{green}2 \textcolor{green}3 \textcolor{red}4$) but $\{1,\dots,5\}$ cannot.$W(2,3)$ implies $\{1,\dots,8\}$ can be 2-colored without mono AP3 (e.g., RRBBRRBB), but $\{1,\dots,9\}$ cannot.

    Conceptual Differences:

    1. Nature of the Unavoidable Pattern:
      • $S(n)$ focuses on avoiding monochromatic additive solutions of the form $x+y=z$. Here, the relationship between the numbers is a direct sum. The values $x, y, z$ do not necessarily need to be in any sequence, just satisfy the sum equation. Often $x, y,$ or $z$ can be the same value (e.g., $1+1=2$).
      • $W(r,k)$ focuses on avoiding monochromatic arithmetic progressions. Here, the numbers must form a sequence with a constant difference ($a, a+d, a+2d, \dots$). The values are inherently distinct (since $d>0$).
    2. Growth Rate: While both numbers are notoriously difficult to compute and grow rapidly, Van der Waerden numbers generally grow much, much faster than Schur numbers. For instance, $S(2)=4$, but $W(2,3)=9$. As the number of colors or the length of the progression/sum increases, this divergence becomes even more pronounced.
    3. Application Domain: While both are part of Ramsey Theory, Schur numbers are more directly connected to questions in number theory concerning partitions of integers and additive properties, whereas Van der Waerden numbers are central to questions about arithmetic structures within sequences.

    In summary, both $S(n)$ and $W(r,k)$ are fundamental examples of Ramsey-type problems that quantify thresholds where specific monochromatic structures become unavoidable. However, they differ in the exact nature of the structure they are seeking (sums vs. arithmetic progressions) and their respective combinatorial complexities.

  4. Prove that Schur numbers grow faster than linearly with respect to $n$.

    Answer to Exercise 4

    Prove that Schur numbers grow faster than linearly with respect to $n$.

    To prove that Schur numbers $S(n)$ grow faster than linearly, we need to show that their growth cannot be bounded by a linear function of the form $f(n) = An + B$ for any constants $A$ and $B$. A common way to demonstrate super-linear growth is to show that the numbers grow at least exponentially.

    Known Lower Bound for $S(n)$

    A well-known lower bound for Schur numbers is: $$S(n) \ge \frac{3^n - 1}{2}$$ Let's verify this bound for the first few known Schur numbers:

    • For $n=1$: $S(1) = 1$. The bound gives $\frac{3^1 - 1}{2} = \frac{2}{2} = 1$. (Matches)
    • For $n=2$: $S(2) = 4$. The bound gives $\frac{3^2 - 1}{2} = \frac{8}{2} = 4$. (Matches)
    • For $n=3$: $S(3) = 13$. The bound gives $\frac{3^3 - 1}{2} = \frac{26}{2} = 13$. (Matches)
    • For $n=4$: $S(4) = 44$. The bound gives $\frac{3^4 - 1}{2} = \frac{80}{2} = 40$. ($44 \ge 40$)
    • For $n=5$: $S(5) = 160$. The bound gives $\frac{3^5 - 1}{2} = \frac{242}{2} = 121$. ($160 \ge 121$)

    This lower bound is proven via constructive methods, often using modular arithmetic or specific coloring schemes.

    Comparison of Exponential vs. Linear Growth

    • Linear Growth: A function $f(n) = An + B$ increases by a constant amount $A$ for each unit increase in $n$. The ratio of consecutive terms $f(n+1)/f(n)$ approaches $1$ as $n \to \infty$.
    • Exponential Growth: A function $g(n) = C \cdot b^n$ (where $b > 1$) increases by a multiplicative factor $b$ for each unit increase in $n$. The ratio of consecutive terms $g(n+1)/g(n) = b$, which is a constant greater than 1. This means exponential functions grow much faster than linear functions.

    Given the lower bound $S(n) \ge \frac{3^n - 1}{2}$, we can see that $S(n)$ grows at least as fast as an exponential function with a base of 3. As $n$ becomes large, the term $\frac{3^n - 1}{2}$ overwhelmingly dominates any linear function. For example, consider:

    • $S(n)$ vs. $f(n) = 100n + 500$

    As $n$ increases, the exponential function $\frac{3^n - 1}{2}$ will eventually surpass any linear function, no matter how large the constants $A$ and $B$ are. Therefore, since $S(n)$ is bounded below by a function that grows exponentially, $S(n)$ itself must grow faster than linearly with respect to $n$.

    This rapid growth is a common characteristic of numbers derived from Ramsey theory and similar combinatorial problems, highlighting their inherent complexity.

  5. Show that for any $n$, $S(n+1) > S(n)$.

    Answer to Exercise 5

    Show that for any $n$, $S(n+1) > S(n)$.

    To show that $S(n+1) > S(n)$, we need to demonstrate that if the set $\{1, \dots, S(n)\}$ can be $n$-colored without a monochromatic solution to $x+y=z$, then the set $\{1, \dots, S(n)+1\}$ can be $(n+1)$-colored without such a solution. This would imply that $S(n+1)$ must be at least $S(n)+1$, hence $S(n+1) > S(n)$.

    Let $k = S(n)$. By definition, there exists an $n$-coloring of the set $\{1, 2, \dots, k\}$ such that there is no monochromatic solution to $x+y=z$. Let's call this coloring $C_n$.

    Now, we want to construct an $(n+1)$-coloring for a set at least as large as $\{1, 2, \dots, k+1\}$. Consider the following $(n+1)$-coloring, let's call it $C_{n+1}$:

    1. For all numbers $i \in \{1, 2, \dots, k\}$, assign them the same color they had in the $n$-coloring $C_n$. That is, $C_{n+1}(i) = C_n(i)$ for $i \in \{1, \dots, k\}$.
    2. Assign the number $k+1$ a brand new, $(n+1)$-th color that has not been used in $C_n$. Let's call this new color `New Color`.

    Now, let's check for monochromatic solutions to $x+y=z$ in this new $(n+1)$-coloring of the set $\{1, 2, \dots, k+1\}$:

    • Case 1: $x, y, z$ are all from the original $n$ colors.
      If $x, y, z \in \{1, \dots, k\}$ and they all have one of the original $n$ colors, then by the definition of $S(n)$, there cannot be a monochromatic solution among these numbers. This part of the coloring remains free of monochromatic solutions.

    • Case 2: One or more of $x, y, z$ is $k+1$.
      If $z = k+1$, then $x+y = k+1$. For this to be a monochromatic solution, $x, y,$ and $k+1$ must all have the `New Color`. However, only $k+1$ has the `New Color`. Numbers $x$ and $y$ must be less than $k+1$ (since $x, y \ge 1$). Thus, $x$ and $y$ would have one of the original $n$ colors, and therefore cannot be the `New Color`.

      If $x=k+1$ or $y=k+1$, this implies $x+y > k+1$ (since $x,y \ge 1$). The sum $z$ would be greater than $k+1$. However, we are only considering numbers up to $k+1$. So, solutions where $x$ or $y$ is $k+1$ are not possible within the set $\{1, \dots, k+1\}$ if $z$ must also be in that set (unless $x=y=(k+1)/2$ and $(k+1)/2$ was assigned the new color, which is not possible as $x,y < k+1$).

      More generally, if $x, y, z$ were all to have the `New Color`, then $x,y,z$ would all have to be $k+1$. But $k+1 + k+1 \neq k+1$. Therefore, no monochromatic solution involving the `New Color` is possible.

    Since we have successfully constructed an $(n+1)$-coloring for the set $\{1, \dots, k+1\} = \{1, \dots, S(n)+1\}$ that avoids monochromatic solutions, it means that the maximal number $N$ for which such a coloring is possible with $n+1$ colors, $S(n+1)$, must be at least $S(n)+1$.

    Thus, $S(n+1) > S(n)$ for any $n$.

  6. Explore the bounds for $S(6)$ and $S(7)$. Explain why exact values are difficult to compute and how SAT solvers might help.

    Answer to Exercise 6

    Explore the bounds for $S(6)$ and $S(7)$. Explain why exact values are difficult to compute and how SAT solvers might help.

    Bounds for $S(6)$ and $S(7)$ (from the provided table)

    From the table in the "Schur numbers for other numbers of colors" section, we have the following lower bounds:

    • $S(6) \ge 536$
    • $S(7) \ge 1680$

    As of current knowledge, these are still lower bounds, and the exact values for $S(6)$ and $S(7)$ remain unknown. This highlights the extreme difficulty in computing these numbers.

    Why Exact Values are Difficult to Compute

    The difficulty in computing exact Schur numbers stems from the inherent combinatorial explosion of the problem:

    1. Exponential Growth: As shown in Exercise 4, Schur numbers grow very rapidly (at least exponentially). For $S(n)$, we need to consider colorings of the set $\{1, 2, \dots, N\}$ where $N$ can be quite large. The number of possible ways to $n$-color a set of $N$ integers is $n^N$. This number grows astronomically fast, making brute-force enumeration impossible even for relatively small $N$.
    2. Constraint Satisfaction: For each coloring, one must check all possible triples $(x,y,z)$ such that $x+y=z$ within the set $\{1, \dots, N\}$ to ensure no monochromatic solution exists. The number of such triples also grows polynomially with $N$ (approximately $N^2/2$ for $x,y \le N$, $z \le N$). This check becomes computationally intensive for large $N$.
    3. No Simple Constructive Pattern: Unlike some other combinatorial problems, there isn't a simple, easily generalizable pattern to construct optimal colorings for Schur numbers as $n$ increases. Finding such a coloring (the 'good' coloring) requires extensive search or sophisticated techniques.
    4. Proof of Impossibility: To prove that $S(n) = N$, one must not only find a valid $n$-coloring for $\{1, \dots, N\}$ but also demonstrate that no valid $n$-coloring exists for $\{1, \dots, N+1\}$. Proving this impossibility (that every coloring of $\{1, \dots, N+1\}$ contains a monochromatic solution) is often the most challenging part, as it requires ruling out an immense number of possibilities.

    How SAT Solvers Might Help

    SAT (Satisfiability) solvers have been instrumental in making breakthroughs in combinatorial problems, most notably in determining $S(5)=160$ in 2018. Here's how they help:

    1. Problem Encoding: The Schur number problem can be translated into a Boolean satisfiability problem (SAT). This involves:
      • Representing each integer $i$ and its assigned color as a Boolean variable (or a set of Boolean variables). For example, if we have $n$ colors, each number $i$ could be associated with $n$ variables $C_{i,1}, C_{i,2}, \dots, C_{i,n}$, where exactly one $C_{i,j}$ is true (meaning $i$ has color $j$).
      • Encoding the constraint $x+y=z$. For every triple $(x,y,z)$ where $x+y=z$ within the range $\{1, \dots, N\}$, a clause is added to the SAT problem. This clause states that $x, y,$ and $z$ cannot all have the same color. For instance, for each color $j$, we would assert that not (Color($x$)=$j$ AND Color($y$)=$j$ AND Color($z$)=$j$).
    2. Automated Proof Search: A SAT solver takes this massive collection of Boolean clauses and attempts to find a truth assignment for all variables that satisfies all clauses. If it finds one, it means a valid coloring exists for $N$. If it proves that no such assignment exists (i.e., the problem is unsatisfiable), it means no valid coloring exists for $N$.
    3. Scalability: Modern SAT solvers are highly optimized and can handle problems with millions of variables and clauses. They use sophisticated algorithms (like CDCL - Conflict-Driven Clause Learning) to prune the search space efficiently. This makes it possible to tackle problems that are far too large for human enumeration or traditional backtracking algorithms.
    4. Computer-Assisted Proof: The determination of $S(5)=160$ was a monumental effort. Researchers used a combination of theoretical insights, problem decomposition, and powerful SAT solvers to search the combinatorial space. The proof ultimately involved generating a satisfiable instance for $N=160$ and an unsatisfiable instance for $N=161$, demonstrating that $S(5)$ was indeed $160$. The unsatisfiability proof for $N=161$ generated by the SAT solver is a massive, highly complex logical certificate that can be independently verified by other tools.

    In essence, SAT solvers provide a powerful computational engine to explore vast combinatorial spaces and provide rigorous, computer-assisted proofs for complex problems like Schur numbers.

  7. Investigate the relationship between Schur numbers and Ramsey numbers $R(3,n)$. Can you find a connection or inequality linking them?

    Answer to Exercise 7

    Investigate the relationship between Schur numbers $S(n)$ and Ramsey numbers $R(3,n)$. Can you find a connection or inequality linking them?

    Understanding Ramsey Numbers

    The Ramsey number $R(s,t)$ is the smallest integer $N$ such that any edge coloring of a complete graph $K_N$ with two colors (say, red and blue) contains either a monochromatic red clique of size $s$ ($K_s$) or a monochromatic blue clique of size $t$ ($K_t$). For example, $R(3,3) = 6$, meaning that in any 2-coloring of the edges of a $K_6$, there must be a monochromatic triangle of either color.

    General Connection within Ramsey Theory

    Both Schur numbers and Ramsey numbers are fundamental concepts within Ramsey Theory. This branch of combinatorics studies the conditions under which order must appear out of disorder. Both types of numbers quantify thresholds where, given a sufficiently large structure that is arbitrarily colored, certain monochromatic substructures are guaranteed to exist.

    • Schur Numbers $S(n)$: Focus on additive structures. They define the largest integer $N$ such that the set $\{1, \dots, N\}$ can be $n$-colored without a monochromatic solution to the equation $x+y=z$.
    • Ramsey Numbers $R(s,t)$: Focus on graph structures. They define the smallest integer $N$ such that any 2-coloring of the edges of $K_N$ guarantees a monochromatic clique of a specified size.

    How Ramsey Theory Proves the Existence of Schur Numbers

    This is a critical point that ties Schur numbers directly to the foundations of Ramsey Theory.

    1. Schur's Theorem (1916): As mentioned in the "Historical Background" section, Issai Schur proved a fundamental result in Ramsey Theory:
      • For any finite coloring of the positive integers, there exists a monochromatic solution to $x + y = z$.

    2. Implication for Existence: This theorem directly implies that Schur numbers $S(n)$ exist for any number of colors $n$. If Schur's Theorem were false, then for some $n$, you could color all positive integers with $n$ colors and never find a monochromatic solution to $x+y=z$. However, Schur's Theorem states this is impossible. Therefore, for any $n$, there must be some maximum integer $N$ such that you can $n$-color $\{1, \dots, N\}$ without a monochromatic solution, but any attempt to $n$-color $\{1, \dots, N+1\}$ will inevitably force a monochromatic solution. This maximal $N$ is precisely $S(n)$.

      In essence, Schur's Theorem, which is a result within Ramsey Theory, guarantees that the problem of finding $S(n)$ is well-defined because there's always a finite boundary beyond which monochromatic solutions are unavoidable.

    3. Ramsey-type Result: Schur's Theorem itself is considered one of the earliest results in Ramsey Theory, predating the more general Ramsey's Theorem. It showcases the core Ramsey principle: sufficient size (of the set of integers) forces specific monochromatic structures (additive solutions).

    Why a Direct Numerical Link to $R(3,n)$ is Not Straightforward

    While Schur's Theorem (a Ramsey-theoretic result) guarantees the existence of $S(n)$, a simple mathematical inequality or formula linking the specific numerical values of $S(n)$ and $R(3,n)$ is not generally found or expected. Here's why:

    1. Different Objects and Patterns:
      • Schur numbers deal with coloring the integers and looking for monochromatic additive triples ($x+y=z$). The underlying structure is arithmetic.
      • Ramsey numbers $R(s,t)$ deal with coloring the edges of a complete graph and looking for monochromatic cliques (subgraphs where all vertices are connected). The underlying structure is graph-theoretic.
    2. Different Meaning of 'n': This is a crucial distinction.
      • In $S(n)$, the parameter $n$ represents the number of colors used for the integers.
      • In $R(3,n)$, the parameter $n$ (assuming standard notation for a 2-color Ramsey number) represents the size of one of the monochromatic cliques being sought (a $K_3$ in one color, and a $K_n$ in the other color). It does not represent the number of colors in the graph problem (which is fixed at 2 for $R(s,t)$).
      Because the 'n' refers to fundamentally different aspects in each definition, a direct numerical comparison or inequality between $S(n)$ and $R(3,n)$ is inherently problematic.
    3. Growth Rates: The growth rates of these numbers differ significantly:
      • $S(n)$ is known to have an exponential lower bound, $S(n) \ge \frac{3^n-1}{2}$, and thus grows exponentially with $n$.
      • $R(3,n)$ (the Ramsey number for a triangle vs. an $n$-clique) is known to grow polynomially with $n$, specifically $R(3,n) \approx \frac{n^2}{\log n}$.
      The disparity in growth rates further underscores that these are distinct functions of their respective parameters and are unlikely to have a simple, direct numerical relationship.

    Conclusion

    The primary connection between Schur numbers $S(n)$ and Ramsey numbers $R(3,n)$ is conceptual: both are foundational examples within Ramsey Theory. Schur's Theorem, a direct result from Ramsey Theory, is what proves that Schur numbers $S(n)$ exist for any given number of colors. It establishes that a finite boundary exists beyond which monochromatic additive solutions are unavoidable. However, due to their distinct problem formulations, the different mathematical objects they apply to, and the different meanings of their parameters, there is no known direct mathematical inequality or simple functional relationship that generally links the numerical values of $S(n)$ and $R(3,n)$. They represent different facets of the broader field of Ramsey Theory.

  8. Design a computer program or algorithm that attempts to construct valid colorings for larger $n$ and discuss its limitations.